//class Solution {
//public:
//    vector<int> grayCode(int n) {
//        vector<int> result(1 << n);
//        for (int i = 0; i < result.size(); i++) {
//            result[i] = (i >> 1) ^ i;
//        }
//        return result;
//    }
//};


//class Solution
//{
//public:
//	void hanota(vector<int>& a, vector<int>& b, vector<int>& c)
//	{
//		dfs(a, b, c, a.size());
//	}
//	void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
//	{
//		if (n == 1)
//		{
//			c.push_back(a.back());
//			a.pop_back();
//			return;
//		}
//		dfs(a, c, b, n - 1);
//		c.push_back(a.back());
//		a.pop_back();
//		dfs(b, a, c, n - 1);
//	}
//};


//class Solution
//{
//public:
//	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
//	{
//		if (l1 == nullptr) return l2;
//		if (l2 == nullptr) return l1;
//		if (l1->val <= l2->val)
//		{
//			l1->next = mergeTwoLists(l1->next, l2);
//			return l1;
//		}
//		else
//		{
//			l2->next = mergeTwoLists(l1, l2->next);
//			return l2;
//		}
//	}
//};


//class Solution
//{
//public:
//	ListNode* reverseList(ListNode* head)
//	{
//		if (head == nullptr || head->next == nullptr) return head;
//		ListNode* newHead = reverseList(head->next);
//		head->next->next = head;
//		head->next = nullptr;
//		return newHead;
//	}
//};


//class Solution
//{
//public:
//	ListNode* swapPairs(ListNode* head)
//	{
//		if (head == nullptr || head->next == nullptr) return head;
//		auto tmp = swapPairs(head->next->next);
//		auto ret = head->next;
//		head->next->next = head;
//		head->next = tmp;
//		return ret;
//	}
//};


//class Solution
//{
//public:
//	bool evaluateTree(TreeNode* root)
//	{
//		if (root->left == nullptr) return root->val == 0 ? false : true;
//		bool left = evaluateTree(root->left);
//		bool right = evaluateTree(root->right);
//		return root->val == 2 ? left | right : left & right;
//	}
//};


class Solution
{
public:
	int sumNumbers(TreeNode* root)
	{
		return dfs(root, 0);
	}
	int dfs(TreeNode* root, int presum)
	{
		presum = presum * 10 + root->val;
		if (root->left == nullptr && root->right == nullptr)
			return presum;
		int ret = 0;
		if (root->left) ret += dfs(root->left, presum);
		if (root->right) ret += dfs(root->right, presum);
		return ret;
	}
};